#include<iostream>
#include<queue>
#include<iomanip>
using namespace std;
int puzzle_subject[17] = {1,2,3,4,5,6,7,8,9,10,16,12,13,14,11,15,-1};
string path = "";
//ʹ��һά�����װδ��λ��ԭpuzzle���հ׿���Ԫ��16��ʾ
//���һλ������ʾ�ϴ���λ�ķ���-1Ϊ��ʼֵ��0Ϊ�ϴ����ƣ�1Ϊ�ϴ����ƣ�2Ϊ�ϴ����ƣ�3Ϊ�ϴ�����
void deep_copy(int* _first, int* _second,int _size = 16)//���
{
	for (int i = 0; i < _size; i++)
	{
		*(_second + i) = *(_first + i);
	}
}

//��ӡ
void show_puzzle(int* _puzzle,int n)
{
	if (_puzzle == NULL)
	{
		cout << "error!" << endl;
		return;
	}
	int cn = 0;
	for (int i = 0; i < n-1; i++)
	{
		cout <<setw(5)<<setfill(' ')<< _puzzle[cn++]; 
		if (cn % 4 == 0)	cout << endl;
	}
	cout << setw(5) << setfill(' ') << "BK" << endl;
}

//���ж��Ƿ��ϸ�������߶�Ӧ��λ���Ƿ�Ϊ��ǰֵ���������ȼ�
int calculate_first(int* _puzzle)
{
	int _first = 0;
	for (int i = 0; i < 16; i++)
	{
		if (*(_puzzle + i) != i + 1) _first++;
	}
	return _first;
}

int find_blank(int* _puzzle)//��λ�װ�λ��
{
	int i = 0;
	for (; _puzzle[i] != 16; i++) {}
	return i;
}

//�����ƺϷ��жϣ��Ƚ���ǰλ����Ϣ��4ȡģ���Ӽ�1�ж��Ƿ���0-3֮�У��ǵĻ��Ϳ�������������
//�����ƺϷ��жϣ��Ӽ�4�ж��Ƿ���0-15֮��
void move(int* _puzzle, queue<int* >&_Q, queue<string>&path,int _position, int last_move)//�ƶ��������Կհ׿�����ƶ�����,��������Ϳհ׿�λ��
{
	int first[4] = {90,90,90,90};//��¼���ȼ�
	int* _move[4] = {NULL,NULL,NULL,NULL};//��¼�ƶ���ı�
	string path_next[4] = { "","","","" };
	string temp = path.front();
	/*int* puzzle_left = NULL;
	int* puzzle_right = NULL;
	int* puzzle_up = NULL;
	int* puzzle_down = NULL;*/
	if (last_move != 1 && _position % 4 - 1 >= 0)//��һ���ƶ���������
	{
		swap(_puzzle[_position], _puzzle[_position - 1]);//����
		first[0] = calculate_first(_puzzle); //��¼���ƺ����ȼ�
		_move[0] = new int[17];
		deep_copy(_puzzle, _move[0]);
		path_next[0] = temp + "->left";
  		_move[0][16] = 0;
		//show_puzzle(_move[0],16);
		swap(_puzzle[_position], _puzzle[_position - 1]);

	}
	if (last_move != 0&&_position % 4 + 1 <= 3)//���ƺϷ�
	{
		swap(_puzzle[_position], _puzzle[_position + 1]);//����
		first[1] = calculate_first(_puzzle); //��¼���ƺ����ȼ�
		_move[1] = new int[17];
		deep_copy(_puzzle, _move[1]);
		path_next[1] = temp + "->right";
		_move[1][16] = 1;
		//show_puzzle(_move[1], 16);
		swap(_puzzle[_position], _puzzle[_position + 1]);
	}
	if (last_move!= 3 && _position - 4 >= 0)//���ƺϷ�
	{
		swap(_puzzle[_position], _puzzle[_position - 4]);//����
		first[2] = calculate_first(_puzzle); //��¼���ƺ����ȼ�
		_move[2] = new int[17];
		deep_copy(_puzzle, _move[2]);
		path_next[2] = temp + "->up";
		_move[2][16] = 2;
		//show_puzzle(_move[2], 16);
		swap(_puzzle[_position], _puzzle[_position - 4]);
	}
	if (last_move!= 2 && _position + 4 <= 15)//���ƺϷ�
	{
		swap(_puzzle[_position], _puzzle[_position + 4]);//����
		first[3] = calculate_first(_puzzle); //��¼���ƺ����ȼ�
		_move[3] = new int[17];
		deep_copy(_puzzle, _move[3]);
		path_next[3] = temp + "->down";
		_move[3][16] = 3;
		//show_puzzle(_move[3], 16);
		swap(_puzzle[_position], _puzzle[_position + 4]);
	}

	int min = 0;
	for (int j = 0; j < 4; j++)
	{
		for (int i = 1; i < 4; i++)
		{
			if (first[min] > first[i])
			{
				min = i;
			}
		}
		if (first[min] == 0)
		{
			while (_Q.size() > 1)	_Q.pop();
			while (path.size() > 1)	path.pop();
			_Q.push(_move[min]);
			path.push(path_next[min]);
			break;
		}
		if (_move[min] != NULL)
		{
			_Q.push(_move[min]);//���ȼ��ߵ��Ƚ�����
			path.push(path_next[min]);
		}
		first[min] = 99;
	}
}


int main()
{
	queue<int*> Q_puzzle;
	queue<string> puzzle_path;
	Q_puzzle.push(puzzle_subject);
	puzzle_path.push("default");
	if (calculate_first(puzzle_subject) != 0)
	{
		int* temp = NULL;
		while (Q_puzzle.size() != 0)
		{
			temp = Q_puzzle.front();
			if (calculate_first(temp) == 0)
				break;
			move(temp, Q_puzzle,puzzle_path,find_blank(temp), temp[16]);
			Q_puzzle.pop();
			puzzle_path.pop();
			//delete[] temp;
		}
		show_puzzle(temp, 16);
		cout << puzzle_path.front() << endl;
	}
	//show_puzzle(temp,16);
	//cout << calculate_first(temp) << endl;
	return 0;
}